/*
 * @Author: liusheng
 * @Date: 2022-06-26 19:17:16
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 19:21:43
 * @Description: 剑指 Offer II 085. 生成匹配的括号
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 085. 生成匹配的括号
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8
 

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

通过次数15,505提交次数18,152
 */

#include "header.h"

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string prefix;
        vector<string> result;
        generateParenthesis(0,0,n,prefix,result);
        return result;
    }
private:
    void generateParenthesis(int open,int close,int totalSize,string & prefix,vector<string> & result)
    {

        if (prefix.size() == totalSize * 2)
        {
            result.push_back(prefix);
            return;
        }

        if (open < totalSize)
        {
            prefix.push_back('(');
            generateParenthesis(open + 1,close,totalSize,prefix,result);
            //traceback
            prefix.pop_back();
        }

        if (close < open)
        {
            prefix.push_back(')');
            generateParenthesis(open,close + 1,totalSize,prefix,result);
            prefix.pop_back();
        }
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if (n == 0)
        {
            result.push_back("");
        }
        else
        {
            for (int c = 0; c < n; ++c)
            {
                for (auto left : generateParenthesis(c))
                {
                    for (auto right : generateParenthesis(n - 1 - c))
                    {
                        result.push_back("(" + left + ")" + right);
                    }
                }
            }
        }
        
        return result;
    }
};